|
In mathematics, Harborth's conjecture states that every planar graph has a planar drawing in which all edge lengths are integers.〔. Reprint of 1994 Academic Press edition; the same name is given to the conjecture in the original 1990 edition.〕〔. Kemnitz and Harborth credit the original publication of this conjecture to .〕〔.〕 This conjecture is named after Heiko Harborth, and (if true) would strengthen Fáry's theorem on the existence of straight-line drawings for every planar graph. For this reason, a drawing with integer edge lengths is also known as an integral Fáry embedding.〔.〕 Despite much subsequent research, Harborth's conjecture remains unsolved.〔.〕 ==Special classes of graphs== Although Harborth's conjecture is not known to be true for all planar graphs, it has been proven for several special kinds of planar graph. One class of graphs that have integral Fáry embeddings are the graphs that can be reduced to the empty graph by a sequence of operations that consist either of removing a vertex of degree at most two or replacing a vertex of degree three by an edge between two of its neighbors. (If such an edge already exists, the degree three vertex can be removed without adding another edge between its neighbors.) For such a graph, a rational Fáry embedding can be constructed incrementally by reversing this removal process, using the facts that the set of points that are at a rational distance from two given points are dense in the plane, and that if three points have rational distance between one pair and square-root-of-rational distance between the other two pairs, then the points at rational distances from all three are again dense in the plane.〔.〕〔.〕 The distances in such an embedding can be made into integers by scaling the embedding by an appropriate factor. Based on this construction, the graphs known to have integral Fáry embeddings include the bipartite planar graphs, (2,1)-sparse planar graphs, planar graphs of treewidth at most 3, and graphs of degree at most four that either contain a diamond subgraph or are not 4-edge-connected.〔〔.〕〔.〕 In particular, the graphs that can be reduced to the empty graph by the removal only of vertices of degree at most two include both the outerplanar graphs and the series-parallel graphs. However, for the outerplanar graphs a more direct construction of integral Fáry embeddings is possible, based on the existence of infinite subsets of the unit circle in which all distances are rational.〔.〕 Additionally, integral Fáry embeddings are known for each of the five Platonic solids.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Harborth's conjecture」の詳細全文を読む スポンサード リンク
|